//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 104 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 
// 👍 1404 👎 0

package leetcode.editor.cn;

/**
 * Java：最长有效括号
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P32_LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new P32_LongestValidParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestValidParentheses(String str) {
            if (str == null || str.length() < 2) {
                return 0;
            }
            char[] strs = str.toCharArray();
            // dp含义：以i位置结尾的字串最长的有效长度为dp[i]
            int[] dp = new int[strs.length];
            int res = 0;
            for (int i = 1; i < strs.length; i++) {
                // 左括号直接0
                if (strs[i] == '(') {
                    continue;
                }
                int imax = 0;
                // 左边有有效值
                int p1 = i - dp[i - 1] - 1;
                if (p1 < 0) {
                    continue;
                }
                char oneLeft = strs[p1];
                if (oneLeft == ')') {
                    continue;
                }
                imax = dp[i - 1] + 2;
                // 有没有往前延申的可能
                int p2 = p1 - 1;
                if (p2 >= 0) {
                    imax += dp[p2];
                }
                dp[i] = imax;
                res = Math.max(res, imax);
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}